Back to course home
0% completed
Vote For New Content
LinkedIn Hard
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Remove Nth Node From End of List
Problem Statement
Given a linked list, remove the last nth node from the end of the list and return the head of the modified list.
Example 1:
- Input: list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
- Expected Output: 1 -> 2 -> 3 -> 5
- Justification: The 2nd node from the end is "4", so after removing it, the list becomes [1,2,3,5].
Example 2:
- Input: list = 10 -> 20 -> 30 -> 40, n = 4
- Expected Output: 20 -> 30 -> 40
- Justification: The 4th node from the end is "10", so after removing it, the list becomes [20,30,40].
Example 3:
- Input: list = 7 -> 14 -> 21 -> 28 -> 35, n = 3
- Expected Output: 7 -> 14 -> 28 -> 35
- Justification: The 3rd node from the end is "21", so after removing it, the list becomes [7,14,28,35].
Constraints:
- The number of nodes in the list is
sz. 1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz
Solution
-
Two-Pass Approach:
- Begin by calculating the length of the linked list. This can be done by traversing the list from the head to the end.
- Once the length is determined, calculate which node to remove by subtracting
nfrom the length. - Traverse the list again and remove the node at the calculated position.
-
One-Pass Approach using Two Pointers:
- Use two pointers,
firstandsecond, and place them at the start of the list. - Move the
firstpointernnodes ahead in the list. - Now, move both
firstandsecondpointers one step at a time until thefirstpointer reaches the end of the list. Thesecondpointer will now bennodes from the end. - Remove the node next to the
secondpointer.
- Use two pointers,
-
Advantage of One-Pass Approach:
- The one-pass approach is more efficient as it traverses the list only once, whereas the two-pass approach requires two traversals.
-
Edge Cases:
- If
nis equal to the length of the list, remove the head of the list.
- If
Algorithm Walkthrough
Using the input list = [1,2,3,4,5], n = 2:
- Initialize two pointers,
firstandsecond, at the head of the list. - Move the
firstpointer 2 nodes ahead. Now,firstpoints to "3" andsecondpoints to "1". - Move both
firstandsecondpointers one step at a time. Whenfirstreaches "5",secondwill be at "3". - The next node to
secondis "4", which is the node to be removed. - Remove "4" by updating the next pointer of "3" to point to "5".
- The modified list is [1,2,3,5].
Code
Java
Saved to Cloud
. . . .
Complexity Analysis
- Time Complexity: O(L) - We traverse the list with two pointers. Here, L is the number of nodes in the list.
- Space Complexity: O(1) - We only used constant extra space.
Remove Nth Node From End of List (Medium)
House Robber II (medium)
Mark as Completed
On this page
Problem Statement
Solution
Algorithm Walkthrough
Code
Complexity Analysis